#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <numeric>
#include <list>
using namespace std;
#define int long long

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	list<int> a;

	return 0;
}


//#define mod 998244353
//int ci[26];
//
//int qp(int a, int b) {
//	int res = 1, base = a;
//	while (b) {
//		if (b & 1)res = (base * res) % mod;
//		base = (base * base) % mod;
//		b >>= 1;
//	}
//	return res;
//}
//int fact(int x) {
//	int res = 1;
//	for (int i = 1; i <= x; i++) {
//		res = (res * i) % mod;
//	}
//	return res;
//}
//
//void solve() {
//	vector<int> c(26);
//	for (int i = 0; i < 26; i++) {
//		cin >> c[i];
//	}
//
//	int s = accumulate(c.begin(), c.end(), 0);
//	vector<int> dp(s + 1);
//	dp[0] = 1;
//	for (int i = 0; i < 26; i++) {
//		if (c[i] == 0)continue;
//		for (int j = s; j >= 0; j--) {
//			if (j + c[i] <= s) {
//				dp[j + c[i]] = (dp[j + c[i]] + dp[j]) % mod;
//			}
//		}
//	}
//
//	int ans = dp[s / 2] * fact(s / 2) % mod * fact((s + 1) / 2) % mod;
//	for (int i = 0; i < 26; i++) {
//		ans = (ans * qp(fact(c[i]), mod - 2)) % mod;
//	}
//	cout << ans << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

//int p[200005];
//bool vis[200005];
//int di[200005];
//int ans;
//
//void dfs(int th) {
//	ans++;
//	vis[th] = 1;
//	if (!vis[p[th]])
//		dfs(p[th]);
//}
//
//void solve() {
//	int n;
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> p[i];
//	}
//	ans = 0;
//	for (int i = 1, x; i <= n; i++) {
//		cin >> x;
//		if (vis[x]) {
//			cout << ans << ' ';
//			continue;
//		}
//		dfs(x);
//		cout << ans << ' ';
//	}
//	cout << '\n';
//	for (int i = 1; i <= n; i++) vis[i] = 0;
//}

//int a[100005];
//void solve() {
//	int n, k, x;
//	cin >> n >> k >> x;
//	int sum = 0;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//		sum += a[i];
//	}
//	int ans = 0;
//	int tmp = 0;
//	for (int i = k - 1; i >= 0; i--) {
//		if (i * sum >= x) {
//			ans += n;
//		}
//		else {
//			tmp = i * sum;
//			break;
//		}
//	}
//	tmp += sum;
//	for (int r = 1; r <= n; r++) {
//		if (tmp >= x)
//			ans++;
//		tmp -= a[r];
//	}
//	cout << ans << '\n';
//}

//void solve() {
//	int n;
//	cin >> n;
//	cout << 2 * n << '\n';
//}

//int n, q;
//int s[100005][2];
//int c[2];
//int ans;
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> q;
//	for (int i = 1; i <= n; i++)s[i][0] = s[i][1] = i & 1;
//	c[1] = c[0] = n;
//	ans = n * n;
//	for (int z = 1, opt, k; z <= q; z++) {
//		cin >> opt >> k;
//		opt--;
//		int dx = (k > 1 && s[k - 1][opt] != s[k][opt]) + (k < n && s[k + 1][opt] != s[k][opt]);
//		int dy = (k > 1 && s[k - 1][opt] == s[k][opt]) + (k < n && s[k + 1][opt] == s[k][opt]);
//		c[opt] -= dx;
//		c[opt] += dy;
//		ans -= dx * c[opt ^ 1];
//		ans += dy * c[opt ^ 1];
//		s[k][opt] ^= 1;
//		cout << ans << '\n';
//	}
//	return 0;
//}